package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/07/23 21:54
 **/
public class Day8_1_Num53_MaxSubArray {
    // 方法一：动态规划
    class Solution {
        public int maxSubArray(int[] nums) {
            int[] dp = new int[nums.length];
            int max = 0;
            for(int i = 0;i < nums.length;i++){
                max = Math.max(max + nums[i],nums[i]);
                dp[i] = max;
            }
            for(int i : dp){
                if(max < i){
                    max = i;
                }
            }
            return max;
        }
    }

    // 方法二：
    class Solution2 {
        public int maxSubArray(int[] nums) {
            int sum = 0;
            int max = Integer.MIN_VALUE;
            for(int i = 0;i < nums.length;i++){
                sum += nums[i];
                if(sum < nums[i]){
                    sum = nums[i];
                }
                if(max < sum) max = sum;
            }
            return max;
        }
    }
}